#ifndef DIRECTED_WEIGHT_GRAPH_H
#define DIRECTED_WEIGHT_GRAPH_H

#include <iostream>
#include <vector>

class DirectedWeightGraph {
public:
    static const int MAX = 1000000;  // 定义最大路径权值。若顶点间路径权值过大，认为两个顶点没有边连接。

    std::vector<int> vertices;          // 顶点集合
    std::vector<std::vector<int>> edges;           // 邻接矩阵，元素值为边的权重

    int V;                   // 顶点个数V
    int E;                   // 边的个数E

    // 构造函数，初始化图的顶点个数等信息
    DirectedWeightGraph(int N);

    // 往图中添加边<u, v>, 权重为weight
    void addEdge(int u, int v, int weight);
};

// 构造函数的定义
DirectedWeightGraph::DirectedWeightGraph(int N) : V(N), E(0) {
    // 初始化顶点(0~V-1)
    for (int i = 0; i < V; ++i) {
        vertices.push_back(i);
    }
    // 初始化边
    edges.resize(V, std::vector<int>(V, MAX));
}

// 添加边函数的定义
void DirectedWeightGraph::addEdge(int u, int v, int weight) {
    edges[u][v] = weight;
    E++;
}

#endif